#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <set>
using namespace std;
struct ThreadNode
{
    int ltag, rtag, data;
    ThreadNode *lchild, *rchild;
    ThreadNode(int data) : data(data), lchild(nullptr), rchild(nullptr), ltag(0), rtag(0){};
};
class ThreadTree
{
protected:
    ThreadNode *root;

public:
    ThreadTree() : root(nullptr){};
    ThreadNode *First(ThreadNode *cur);
    ThreadNode *Last(ThreadNode *cur);
    ThreadNode *Next(ThreadNode *cur);
    ThreadNode *Prior(ThreadNode *cur);
    void createInThread(ThreadNode *cur, ThreadNode *&pre);
    void InOrder();
};
ThreadTree::First(ThreadNode *cur)
{
    ThreadNode *p = cur;
    while (cur->ltag == 0)
        p = p->lchild;
    return p;
}
ThreadTree::Next(ThreadNode *cur)
{
    ThreadNode *p = cur->rchild;
    if (cur->rtag == 0)
        return First(p);
    else
        return p;
}
ThreadTree::Last(ThreadNode *cur)
{
    ThreadNode *p = cur;
    while (p->rtag == 0)
        p = p->rchild;
    return p;
}
ThreadTree::Prior(ThreadNode *cur)
{
    ThreadNode *p = cur->lchild;
    if (cur->ltag == 0)
        return Last(p);
    else
        return p;
}
ThreadTree::InOrder()
{
    ThreadNode *p = root;
    for (p = First(root); p != nullptr; p = Next(p))
        cout << p->data << " " << endl;
}
ThreadTree::createInThread(ThreadNode *cur, ThreadNode *&pre)
{
    if (cur == nullptr)
        return;
    createInThread(cur->lchild, pre);
    if (cur->lchild == nullptr)
    {
        cur->lchild = pre;
        cur->ltag = 1;
    }
    if (pre != nullptr && pre->rchild == nullptr)
    {
        pre->rchild = cur;
        pre->rtag = 1;
    }
    pre = cur;
    createInThread(cur->rchild, pre);
}